package site.wanjiahao.list;

import java.util.Iterator;

// 双向链表相对于单向列表，查询元素将近快了一半，可以从队头，也可以从队尾查询
public class LinkedList<E> extends AbstractList<E> implements Iterable<E> {

    // 头结点
    private Node<E> first;

    // 尾节点
    private Node<E> last;

    @Override
    public void add(E ele) {
        add(size, ele);
    }

    @Override
    public E get(int index) {
        rangeCheck(index);
        return node(index).ele;
    }

    @Override
    public E set(int index, E ele) {
        rangeCheck(index);

        Node<E> node = node(index);
        E oldEle = node.ele;
        node.ele = ele;
        return oldEle;
    }

    @Override
    public void add(int index, E ele) {
        rangeCheckForAdd(index);
        Node<E> setNode;
        //  添加元素
        if (index == 0) {
            if (index == size) {
                // 第一次添加
                setNode = new Node<>(ele, null, null);
                last = setNode;
            } else {
                // 非第一添加
                setNode = new Node<>(ele, first, null);
            }
            // 链表尾
            first = setNode;
        } else {
            if (index == size) {
                // 添加链表尾部，存在元素
                setNode = new Node<>(ele, null, last);
                last.next = setNode;
                last = setNode;
            } else {
                // 通用位置
                Node<E> prev = node(index - 1);
                Node<E> old = prev.next;
                setNode = new Node<>(ele, old, prev);
                prev.next = setNode;
                old.prev = setNode;
            }
        }
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        Node<E> old = first;
        if (index == 0) {
            // 删除链表首
            first = first.next;
        } else {
            if (index == size - 1) {
                old = last;
                // 删除链表尾部
                last = last.prev;
            } else {
                // 通用情况
                Node<E> prev = node(index - 1);
                old = prev.next;
                Node<E> next = old.next;
                prev.next = next;
                next.prev = prev;
            }
        }
        size--;
        return old.ele;
    }

    @Override
    public int indexOf(E ele) {
        if (ele != null) {
            for (int i = 0; i < size; i++) {
                if (ele.equals(get(i))) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (null == get(i)) {
                    return i;
                }
            }
        }
        return NOT_FOUND_ELEMENT;
    }

    @Override
    public void clear() {
        // 清空内存数据
        first = null;
        last = null;
        size = 0;
    }

    @Override
    public Iterator<E> iterator() {
        return new DefaultIter();
    }

    @Override
    public String toString() {
        int end = size - 1;
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(get(i));
            if (i != end) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    public Node<E> node(int index) {
        Node<E> node;
        int end = size - 1;
        // 判断当前索引在size的那个区域
        if (index > (end >> 1)) {
            node = last;
            // 右半区域 后往前
            while (index++ < end ) {
                node = node.prev;
            }
        } else {
            node = first;
            // 左半区域
            while (index-- >= 1 ) {
                node = node.next;
            }
        }
        return node;
    }


    /**
     * 内部类Node对象
     *
     * @param <E>
     */
    private static class Node<E> {

        private E ele;

        private Node<E> next;

        private Node<E> prev;

        public Node(E ele, Node<E> next, Node<E> prev) {
            this.ele = ele;
            this.next = next;
            this.prev = prev;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "ele=" + ele +
                    ", next=" + next +
                    ", prev=" + prev +
                    '}';
        }
    }
}
